package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/3/1.
 */
public class LC33 {

    public int search(int[] nums, int target) {
        return midSearch(nums, 0, nums.length - 1, target);
    }

    public int midSearch(int[] arr, int lb, int ub, int target) {
        if (null == arr || arr.length <= 0 || ub < lb) {
            return -1;
        }

        if (ub - lb <= 1) {
            if (arr[ub] == target) {
                return ub;
            }
            if (arr[lb] == target) {
                return lb;
            }
            return -1;
        }

        int mid = (ub + lb) / 2;
        if (target == arr[mid]) {
            return mid;
        }

        if (arr[mid] < arr[lb]) {
            if (target >= arr[mid] && target <= arr[ub]) {
                return midSearch(arr, mid + 1, ub, target);
            } else {
                return midSearch(arr, lb, mid - 1, target);
            }

        }

        if (arr[mid] > arr[lb]) {
            if (target >= arr[lb] && target <= arr[mid]) {
                return midSearch(arr, lb, mid - 1, target);
            } else {
                return midSearch(arr, mid + 1, ub, target);
            }
        }

        return -1;
    }


    public static void main(String[] args) {
        LC33 an = new LC33();
        int arr[] = {1, 3};
        System.out.println(an.search(arr, 3));
    }
}
